package 算法.leetcode.bytedance.字符串;

/**
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 *
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 * @author lchenglong
 * @date 2023/2/14
 */
public class 字符串的排列 {
    public static class Solution {

        public static void main(String[] args) {

        }
        public boolean checkInclusion(String s1, String s2) {
            // 边界条件
            if (s1 == null || s2 == null || s2.length() == 0 || s1.length()>s2.length())return false;
            // 定义s1的欠账表, 最终由s2来还
            int[] cnt = new int[26];
            for (int i=0;i<s1.length();i++){
                cnt[s1.charAt(i)-'a']++;
            }

            // 遍历s2, 在s2的某个区间内的每个字符串的数量刚好等于s1的每个字符串的数量,即满足条件
            int l=0,r=0;
            for (;r<s2.length();r++){
                int idx = s2.charAt(r) - 'a';
                // 还s1的账
                ++cnt[idx];
                while (cnt[idx]>0){
                    // 当前区间可还账,开始拆了东墙补西墙
                    --cnt[s2.charAt(l)-'a'];
                    ++l;
                }
                // 跳出来之后,说明能还的都还了,看看是否满足条件,不满足,继续区间右移
                if (r-l+1 == s1.length())return true;
            }
            return false;
        }
    }
}
